package hashTable

// 前缀和+hash表
/*
时间复杂度：O(n)
空间复杂度：O(n) 来源于哈希表的内存开销
 */
func subarraySum(nums []int, k int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	// 前缀和
	preSum, count := 0, 0
	// 哈希表
	m := make(map[int]int)
	m[0] = 1
	for _, v := range nums {
		preSum += v
		if _, ok := m[preSum-k]; ok {
			count += m[preSum-k]
		}
		m[preSum]++
	}
	return count
}

// 暴力破解
func subarraySum1(nums []int, k int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	count := 0
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum == k {
				count++
			}
		}
	}
	return count
}
